\newif\iffullver
\fullverfalse
\fullvertrue %last one wins

\newcommand{\fullonly}[1]{\iffullver#1\fi}
\newcommand{\shortonly}[1]{\iffullver\else#1\fi}

\shortonly{\documentclass{llncs}}
\fullonly{\documentclass[11pt,letterpaper]{llncs}}


\newif\ifshowhl
\showhltrue % show highlighting of new sections (for harmonic)

\newcommand{\highlight}[1]{\ifshowhl \hl{NEW SECTION} #1 \hl{END NEW 
SECTION}\else#1\fi}

\fullonly{\usepackage[left=1in,right=1in,top=1in,bottom=1in]{geometry}}

\shortonly{\pagestyle{headings}}
\fullonly{\pagestyle{plain}}

\usepackage{soul} % for highlighting text
% \usepackage{typearea}
% \paperwidth 8.5in \paperheight 11in
% \typearea{15}

\usepackage{etoolbox} % for if statements

\usepackage[section]{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{comment}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{amsmath,amssymb}
\newcommand{\commented}[1]{\hspace{3em}{// #1}}
\newcommand{\figscale}{0.20} % use this to adjust sizes of figures

\usepackage{ifpdf}
\usepackage{color}
\fullonly{\usepackage{times}}
\usepackage{paralist}

\definecolor{Darkblue}{rgb}{0,0,0.4}
\definecolor{Brown}{cmyk}{0,0.81,1.,0.60}
\definecolor{Purple}{cmyk}{0.45,0.86,0,0}
\newcommand{\mydriver}{hypertex}
\ifpdf
 \renewcommand{\mydriver}{pdftex}
\fi
\usepackage[breaklinks,\mydriver]{hyperref}
\hypersetup{colorlinks=true,%pdfborder={1 1 1 [3]},%
            citebordercolor={.6 .6 .6},linkbordercolor={.6 .6 .6},%
citecolor=Darkblue,urlcolor=black,linkcolor=Darkblue,pagecolor=black}
\newcommand{\lref}[2][]{\hyperref[#2]{#1~\ref*{#2}}}

\fullonly{
\newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}}
\renewenvironment{proof}{\begin{trivlist} \item[\hspace{\labelsep}{\bf
\noindent Proof.\/}] }{\end{trivlist}}%
}



\newcommand{\aside}[1]{\makebox[1.5in][r]{#1}}

\newcommand{\klnote}[1]{\refstepcounter{note}$\ll${\bf Kevin~\thenote:} {\sf 
#1}$\gg$\marginpar{\tiny\bf KL~\thenote}}
\newcommand{\aanote}[1]{\refstepcounter{note}$\ll${\bf Amir~\thenote:} {\sf 
#1}$\gg$\marginpar{\tiny\bf AA~\thenote}}




\begin{document}

\begin{comment}

\section{Contractions}

Define the problem \emph{Exact-Weight-$H$} to be the following: given a graph 
$G$ on $n$ nodes, a subgraph $H$, a target weight $K$, and a weight function $w 
: E \rightarrow \mathbb{Z}$, determine if there exists a (non-induced) subgraph 
of $G$ where the sum of the weights on the edges is exactly $K$.

Define the \emph{$H$-structured graph} of $G$ to be the following: for each node 
of $H$, create a partition $P_1, \ldots, P_k$, where $P_i$ consists of $n$ 
nodes. Let $V_{i,j}$ be the $j$th node of the $P_i$. Then, for each pair of 
partitions $P_i$ and $P_j$, we put an edge between $V_{i,k}$ and $V_{j,\ell}$ of 
weight $w(k,\ell)$ (from the original graph $G$) if and only if the edge $(i,j)$ 
exists in $H$. Thus, the resulting graph is a $k$-partite graph with $kn$ nodes and $|E(H)|\cdot |E(V)|$ edges. 

Now, let $T = \{k_1, \ldots, k_m\}$ be a set of integers of such that, for any 
multiset $T'$ that is a subset of $T$, the sum of all integers of $T'$ is not 
equal to the sum of all integers of $T$. Furthermore, all integers are above some 
threshold $W \cdot |E|$, where $W$ is the maximum weight of any edge in $G$.

Let $T$ be such that it has $m = |E(H)|$ elements. Then, for each edge $(i,j) \in E(H)$, we 
associate an element $k_{i,j} \in T$, and add $k_{i,j}$ to the weights of all edges in $G'$ between 
partitions $P_i$ and $P_j$.


\begin{property}
	For any subgraph $H'$ which can be obtained from $H$ via edge deletions and vertex contractions, there exists an $H'$ in $G$ of weight $K$ if and only if there exists an $H'$ in $G[H]$ of weight $K$.
\end{property}

\begin{property}
	For any subgraph $H$, for any distinct-sum set $T$, the following are equivalent:
	\begin{enumerate}
		\item There is a well-formed $H$ in $G[H]$ of weight $K$.
		\item There exists a well-formed $H$ in $G[H,T]$ of weight $K + w(T)$.
		\item There exists an $H$ in $G[H,T]$ of weight $K + w(T)$.
	\end{enumerate}
\end{property}

\begin{property}
	Let $H'$ be a graph obtained by deleting an edge $e^*$ from $H$.
	There is an $H'$ of weight $K$ if and only if there is a well-formed $H$ of weight $K$ in $G[H]_{e^*}$ (TODO: define this).
\end{property}

\begin{property}
	
\end{property}

\begin{property}
	\label{prop:p1}
	Let $w(T)$ be the sum of all elements in $T$. A set $S$ of edges corresponds to an 
	$H$ of weight $K + w(T)$ in the $H$-structured graph of $G$ if and only if:
	\begin{enumerate}
		\item For every edge $(i,j) \in E(H)$, $S$ uses exactly one edge between $P_i$ and $P_j$, and 
		\item the set $S$ forms an $H$ of weight $K$ in the original graph $G$.
	\end{enumerate}
\end{property}

\begin{proof}
	TODO
\end{proof}

\begin{lemma}
	Let $H'$ be a subgraph of $H$ which can be obtained via an edge deletion. 
	Then, an $n^\alpha$ time algorithm for Exact-Weight-$H$ implies an 
	$O( (k \cdot n)^\alpha)$ time algorithm for Exact-Weight-$H'$.
\end{lemma}

\begin{proof}
	FIXE
	Let $e^* = (i,j)$ be the edge that is deleted from $H$ to result in $H'$.	Let 
	$G$ be the graph for the instance of Exact-Weight-$H'$, and let $|H'| = k$. 
	Consider the $H$-structured graph of $G$, where between partitions $P_i$ and 
	$P_j$ (associated with edge $e^*$), we set all edge weights to be $k_{i,j}$ where $k_{i,j}$ is the element of $T$ associated with $P_i$ and $P_j$. Then, 
	we solve Exact-Weight-$H$ on the resulting graph (call it $G'$), 
	which yields the answer for Exact-Weight-$H'$.

	To prove the correctness of the construction, we first show that if there 
	exists an Exact-Weight-$H$ of total weight $K + w(T)$ in $G'$, then there 
	exists an Exact-Weight-$H'$ of total weight $K$ in $G$. Let $S$ be the set of 
	edges corresponding to the $H$ of weight $K + w(T)$ in $G'$. Then, by 
	Property~\ref{prop:p1} of the $H$-structured graph, the set $S$ forms an $H$ 
	in $G$ with weight $K$. Note that $e^* \in S$ has weight $0$. Thus, the set $S 
	\setminus \{e^*\}$ forms an $H'$ in $G$ of weight $K$.

	For the other direction, assume that there exists an $H'$ in $G$ of weight 
	$K$, and let $S$ be the set of edges that form this $H'$. Consider the 
	$H$-structured graph of $G$. First, we claim that for each edge $(i,j) \in H'$, 
	$S$ uses exactly one edge 
	between partitions $P_i$ and $P_j$ in $G'$. This follows from the property 
	of the set $T$ chosen for $G'$. Therefore, by Property~\ref{prop:p1}, $S$ 
	corresponds to an $H'$ of weight $K + w(T)$ in the $H$-structured graph. 
	Note that all edges between $P_i$ and $P_j$
	are of weight $k_{i,j}$, where $e^* = (i,j)$. Thus, the set $S \cup \{e^*\}$ also 
	has weight $K + w(T)$, and it forms an $H$ in the $H$-structured graph $G'$.
	\qed
\end{proof}



\begin{lemma}
	Let $H'$ be a subgraph of $H$ which can be obtained via a vertex contraction. 
	Then, an $n^\alpha$ time algorithm for Exact-Weight-$H$ implies an 
	$O( (k \cdot n)^\alpha)$ time algorithm for Exact-Weight-$H'$.
\end{lemma}

\begin{proof}
	Let $u$ and $v$ be the vertices to be contracted in $H$. We claim that the 
	interesting case for this proof is when $(u,v) \not\in E(H)$, and $N(u) \cap 
	N(v) = \emptyset$. For the other cases, we first show how to reduce them to 
	the interesting case. Suppose $(u,v) \in E(H)$. Then, we apply the previous 
	lemma to remove $(u,v)$. Also, while $N(u) \cap N(v) \neq \emptyset$, pick a 
	vertex $w \in N(u) \cap N(v)$ and remove the edge $(u,w)$.
	
	Therefore, we can now assume that $(u,v) \not\in E(H)$ and $N(u) \cap N(v) = 
	\emptyset$. Note that we can assume without loss of generality that 
	$|N(u)|,|N(v)| \geq 1$.


\end{proof}

\end{comment}




%%%%%%%%%%%%%%%%%%%% POSITIVE RESULTS %


\section{ Preliminaries}

\def \EWI{Exact-Weight-Injective-H }
\begin{definition}[The \EWI problem]
Given an edge-weighted graph G, an unweighted graph $H$, a target weight K, does there exist a mapping $\varphi : V(H) \rightarrow V(G)$ such that:
\begin{enumerate}
	\item For all $u,v \in V(H)$, $(u,v) \in E(H)$ implies $( \varphi(u), \varphi(v)) \in E(G)$
	\item $\sum_{(u,v) \in E(H)} w(\varphi(u), \varphi(v)) = K$
	\item $\varphi$ is injective
\end{enumerate}
\end{definition}

\def \EWNI{Exact-Weight-Non-Injective-H } % maybe we should just call it Exact-Weight-H... 
\begin{definition}[The \EWNI problem]
As above, but $\varphi$ doesn't have to be injective.
%% Amir: or should we just repeat the def again?
\end{definition}

\def \Hstruct{H-Structured-Graph }
\begin{definition}[\Hstruct]
Given a graph $G$, define the \Hstruct of $G$, $H[G]$, to be the following: for each node 
of $H$, create a partition $P_1, \ldots, P_k$, where $P_i$ consists of $n$ 
nodes. Let $v_{i,j}$ be the $j$th node of the $P_i$. Then, for each pair of 
partitions $P_i$ and $P_j$, we put an edge between $v_{i,k}$ and $v_{j,\ell}$ of 
weight $w(k,\ell)$ (from the original graph $G$) if and only if the edge $(i,j)$ 
exists in $H$. 
%% Amir: I think we should try to make this definition clearer. later.
\end{definition}
% (does not mess with weights, but includes weights)

Note that the resulting graph, $G[H]$, is a $k$-partite graph with $kn$ nodes and $|E(H)|\cdot |E(V)|$ edges. 



\def \EWWF{Exact-Weight-Well-Formed-H }
\begin{definition}[The \EWWF problem]
	Given an \Hstruct, find an \EWI solution that uses every "partition" exactly 
	once. Formally, we require the mapping $\varphi$ to satisfy requirements 1 and 
	2 and the following: $\forall v \in V(H) : \varphi(v) \in P_v$. 
\end{definition}

%% Amir: maybe we should give the 1,2,3 requirements names and then the definitions will be nicer.
% note: at the moment, \EWWF is non-injective.
%We will show that this problem is equivalent to the \EWI problem.


\def \DSS{Distinct-Sum-Set }
\begin{definition}[\DSS]
	A set $T= \{ t_1 , \ldots , t_m \}$ is a $k$-\DSS with minimum value above 
	$\tau$ of size $m$, if (1) $\forall t_i \in T a_i > \tau$ and (2) for every 
	multiset $T'$ of size $m$ that is a subset of $T$, but $T' \neq T$, 
	$\sum\limits_{a\in T'}{a} \neq \sum\limits_{a\in T} {a}$.
\end{definition}
% We will use this later.

\def \Kevin{"Kevin Minor" } % name needed
\begin{definition}[\Kevin]
	A graph $H'$ is called a \Kevin of graph $H$ if it can be obtained from $H$ 
	via (any number of) the following operations:
	\begin{itemize}
		\item Edge deletion:
		\item Vertex contraction: TODO % name needed here too
	\end{itemize} 
\end{definition}


\section{ Positive results}

\subsection{algorithm using k-sum}
\begin{theorem}[Independent Set Algorithm]
	Let $H$ be a graph on $k$ nodes, with an independent set of size $s$. 
	Exact-Weight-$H$ can be solved in time $O(n ^ { k - \lfloor s/2 \rfloor } )$.
\end{theorem}

\begin{proof}
	TODO
\end{proof}

\subsection{algorithm using hashing}
\begin{theorem}[Cut Algorithm]
	Let $H$ be a graph, define $\gamma = \min \limits_{ S \subseteq V } { \max \{ 
	|S \cup N(S)|, |\bar{S} \cup N(\bar{S})| \} }$. Exact-Weight-$H$ can be solved 
	in time $O(n ^ \gamma )$.
\end{theorem}

\begin{proof}
	TODO
\end{proof}



\section{ Negative results}

\begin{theorem}[Main Theorem]
	Let $H'$ be a \Kevin of a graph $H$ on $k$ nodes. For every $\alpha>0$, there 
	exists $f:\mathbb{N} \rightarrow \mathbb{N}$, such that:
	An $n^\alpha$ time algorithm for \EWI implies an 
	$O( f(k) \cdot n^\alpha)$ time algorithm for Exact-Weight-Injective-$H'$.
\end{theorem}

We will need the following lemmas in order to prove this theorem...

\subsection{ Equivalences between versions of the problem }

\begin{proposition} [ \EWI $\equiv$ \EWNI ]
	For every $\alpha>0$, there exist $f_1,f_2:\mathbb{N} \rightarrow \mathbb{N}$, 
	such that: There is an $O(f_1(k)\cdot n^\alpha)$ time algorithm for the \EWI 
	problem, if and only if there is an $O(f_2(k)\cdot n^\alpha )$ time algorithm 
	for the \EWNI problem.
\end{proposition}
\begin{proof}
	TODO
\end{proof}

\begin{proposition} [  \EWWF $\equiv$ \EWNI ]
	For every $\alpha>0$, there exist $f_1,f_2:\mathbb{N} \rightarrow \mathbb{N}$, 
	such that: There is an $O(f_1(k)\cdot n^\alpha)$ time algorithm for the \EWWF 
	problem, if and only if there is an $O(f_2(k)\cdot n^\alpha )$ time algorithm 
	for the \EWNI problem.
\end{proposition}
\begin{proof}
	TODO - we know 1 direction. is the other one true???
	%use distinct sum sets. define G[H,T] or something
\end{proof}

%Amir: I think these are the only two relations we need for the rest next lemmas.

\subsection{ Edge Deletions }
%lemma
%proof
\subsection{ Vertex Contractions }
%lemma
%proof

%%% Proof of Main Theorem here.

\subsection{ Claw number}

\subsection{Clique number}

\subsection{ Special interesting cases }

\end{document}
